Mi manual de algoritmos/version_maraton_interuniversitaria_2008-2/src/grafos/kruskal.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$iostream$>$}} \\
   6 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$vector$>$}} \\
   7 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$algorithm$>$}} \\
   8 \mbox{} \\
   9 \mbox{}\textbf{\textcolor{Blue}{using}}\ \textbf{\textcolor{Blue}{namespace}}\ std\textcolor{BrickRed}{;} \\
  10 \mbox{} \\
  11 \mbox{}\textit{\textcolor{Brown}{/*}} \\
  12 \mbox{}\textit{\textcolor{Brown}{Algoritmo\ de\ Kruskal,\ para\ encontrar\ el\ árbol\ de\ recubrimiento\ de\ mínima\ suma.}} \\
  13 \mbox{}\textit{\textcolor{Brown}{*/}} \\
  14 \mbox{} \\
  15 \mbox{}\textbf{\textcolor{Blue}{struct}}\ edge\textcolor{Red}{\{} \\
  16 \mbox{}\ \ \textcolor{ForestGreen}{int}\ start\textcolor{BrickRed}{,}\ end\textcolor{BrickRed}{,}\ weight\textcolor{BrickRed}{;} \\
  17 \mbox{}\ \ \textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Blue}{operator}}\ \textcolor{BrickRed}{$<$}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ edge\ \textcolor{BrickRed}{\&}that\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{const}}\ \textcolor{Red}{\{} \\
  18 \mbox{}\ \ \ \ \textit{\textcolor{Brown}{//Si\ se\ desea\ encontrar\ el\ árbol\ de\ recubrimiento\ de\ máxima\ suma,\ cambiar\ el\ $<$\ por\ un\ $>$}} \\
  19 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\ weight\ \textcolor{BrickRed}{$<$}\ that\textcolor{BrickRed}{.}weight\textcolor{BrickRed}{;} \\
  20 \mbox{}\ \ \textcolor{Red}{\}} \\
  21 \mbox{}\textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
  22 \mbox{} \\
  23 \mbox{} \\
  24 \mbox{} \\
  25 \mbox{}\textit{\textcolor{Brown}{/*\ Union\ find\ */}} \\
  26 \mbox{}\textcolor{ForestGreen}{int}\ p\textcolor{BrickRed}{[}\textcolor{Purple}{10001}\textcolor{BrickRed}{],}\ rank\textcolor{BrickRed}{[}\textcolor{Purple}{10001}\textcolor{BrickRed}{];} \\
  27 \mbox{}\textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{make$\_$set}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ x\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ x\textcolor{BrickRed}{,}\ rank\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;}\ \textcolor{Red}{\}} \\
  28 \mbox{}\textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{link}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ x\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ y\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ rank\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$>$}\ rank\textcolor{BrickRed}{[}y\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{?}\ p\textcolor{BrickRed}{[}y\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ x\ \textcolor{BrickRed}{:}\ p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ y\textcolor{BrickRed}{,}\ rank\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{==}\ rank\textcolor{BrickRed}{[}y\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{?}\ rank\textcolor{BrickRed}{[}y\textcolor{BrickRed}{]++:}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;}\ \textcolor{Red}{\}} \\
  29 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ x\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ \textbf{\textcolor{Blue}{return}}\ x\ \textcolor{BrickRed}{!=}\ p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{?}\ p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{])}\ \textcolor{BrickRed}{:}\ p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{];}\ \textcolor{Red}{\}} \\
  30 \mbox{}\textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{merge}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ x\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ y\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ \textbf{\textcolor{Black}{link}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}x\textcolor{BrickRed}{),}\ \textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}y\textcolor{BrickRed}{));}\ \textcolor{Red}{\}} \\
  31 \mbox{}\textit{\textcolor{Brown}{/*\ End\ union\ find\ */}} \\
  32 \mbox{} \\
  33 \mbox{} \\
  34 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{main}}\textcolor{BrickRed}{()}\textcolor{Red}{\{} \\
  35 \mbox{}\ \ \textcolor{ForestGreen}{int}\ c\textcolor{BrickRed}{;} \\
  36 \mbox{}\ \ cin\ \textcolor{BrickRed}{$>$$>$}\ c\textcolor{BrickRed}{;} \\
  37 \mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}c\textcolor{BrickRed}{-\/-)}\textcolor{Red}{\{} \\
  38 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ n\textcolor{BrickRed}{,}\ m\textcolor{BrickRed}{;} \\
  39 \mbox{}\ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ n\ \textcolor{BrickRed}{$>$$>$}\ m\textcolor{BrickRed}{;} \\
  40 \mbox{}\ \ \ \ vector\textcolor{BrickRed}{$<$}edge\textcolor{BrickRed}{$>$}\ e\textcolor{BrickRed}{;} \\
  41 \mbox{}\ \ \ \ \textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\ total\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  42 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}m\textcolor{BrickRed}{-\/-)}\textcolor{Red}{\{} \\
  43 \mbox{}\ \ \ \ \ \ edge\ t\textcolor{BrickRed}{;} \\
  44 \mbox{}\ \ \ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ t\textcolor{BrickRed}{.}start\ \textcolor{BrickRed}{$>$$>$}\ t\textcolor{BrickRed}{.}end\ \textcolor{BrickRed}{$>$$>$}\ t\textcolor{BrickRed}{.}weight\textcolor{BrickRed}{;} \\
  45 \mbox{}\ \ \ \ \ \ e\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{(}t\textcolor{BrickRed}{);} \\
  46 \mbox{}\ \ \ \ \ \ total\ \textcolor{BrickRed}{+=}\ t\textcolor{BrickRed}{.}weight\textcolor{BrickRed}{;} \\
  47 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  48 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{sort}}\textcolor{BrickRed}{(}e\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{begin}}\textcolor{BrickRed}{(),}\ e\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{end}}\textcolor{BrickRed}{());} \\
  49 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$=}n\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  50 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{make$\_$set}}\textcolor{BrickRed}{(}i\textcolor{BrickRed}{);} \\
  51 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  52 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}e\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  53 \mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{int}\ u\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}start\textcolor{BrickRed}{,}\ v\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}end\textcolor{BrickRed}{,}\ w\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}weight\textcolor{BrickRed}{;} \\
  54 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}u\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{!=}\ \textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}v\textcolor{BrickRed}{))}\textcolor{Red}{\{} \\
  55 \mbox{}\ \ \ \ \ \ \ \ \textit{\textcolor{Brown}{//xprintf("{}Joining\ \%d\ with\ \%d\ using\ weight\ \%d\textbackslash{}n"{},\ u,\ v,\ w);}} \\
  56 \mbox{}\ \ \ \ \ \ \ \ total\ \textcolor{BrickRed}{-=}\ w\textcolor{BrickRed}{;} \\
  57 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Black}{merge}}\textcolor{BrickRed}{(}u\textcolor{BrickRed}{,}\ v\textcolor{BrickRed}{);} \\
  58 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  59 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  60 \mbox{}\ \ \ \ cout\ \textcolor{BrickRed}{$<$$<$}\ total\ \textcolor{BrickRed}{$<$$<$}\ endl\textcolor{BrickRed}{;} \\
  61 \mbox{} \\
  62 \mbox{}\ \ \textcolor{Red}{\}} \\
  63 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  64 \mbox{}\textcolor{Red}{\}} \\
  65
  66 } \normalfont\normalsize